#include "CalculatorDec.h"
#include <QtDebug>

CalculatorDec::CalculatorDec() : m_result("")
{

#if 0 // test

    QQueue<QString> r = split("-9+(3.1-1)*5.3");
    for (int i=0;i<r.length();i++)
    {
        qDebug() << r[i];
    }

    qDebug()<<"****";
    QQueue<QString> output;
    transform(r,output);
    for(int i=0;i<output.length();i++)
    {
        qDebug()<< output[i];
    }

    qDebug()<<"****";
    qDebug()<< calculate(output);

#endif
}


bool CalculatorDec::isDigitOrDot(QChar c)
{
    return ( (('0'<=c) && (c<='9')) || (c=='.'));
}

bool CalculatorDec::isOperator(QString c)
{
    return ( (c=='+') || (c=='-') || (c=='*') ||(c=='/') );
}

bool CalculatorDec::isSymbol(QChar c)
{
    return isOperator(c) || (c=='(') || (c==')');
}

bool CalculatorDec::isSign(QChar c)
{
    return (c=='+') || (c=='-');
}
bool CalculatorDec::isNumber(QString s)
{
    bool ret = false;

    s.toDouble(&ret);

    return ret;
}

bool CalculatorDec::isLeft(QString s)
{
    return s=="(";
}

bool CalculatorDec::isRight(QString s)
{
    return s==")";
}

int CalculatorDec::priority(QString s)
{
    int ret = 0;

    if (s=="+" || s=="-")
    {
        ret = 1;
    }

    if (s=="*" || s=="/")
    {
        ret = 2;
    }

    return ret;
}


bool CalculatorDec::match(QQueue<QString> exp)
{
    bool ret = true;
    int len = exp.length();
    QStack<QString> stack;

    for ( int i=0;i<len;i++ )
    {
        if ( isLeft(exp[i]) )
        {
            stack.push(exp[i]);
        }
        else if ( isRight(exp[i]) )
        {
            if ( !stack.isEmpty() && isLeft( stack.top() ) )
            {
                stack.pop();
            }
            else
            {
                ret = false;
                break;
            }
        }
    }

    return ret;
}

/* 获取中缀表达式 *
   将输入的表达式用空格分离出运算符和数字
   eg. -9+(3-1)*5 -> -9 3 1 - 5 +

    算法:以符号作为标志对表达式的字符逐个访问
    - 定义累计变量num
    - 当前字符exp[i]为数字或小数点时：
        累计: num+=exp[i]
    - 当前字符exp[i]为符号时：
        num为运算数，分离并保存到队列
        若exp[i]为正负号：
            累计符号为+和-：num+=exp[i]
        若exp[i]为运算付：
            分离并保存到队列
*/
QQueue<QString> CalculatorDec::split(const QString exp)
{
    QQueue<QString> ret;
    QString num = "";
    QString pre = "";

    /* for each QChar in exp */
    for (int i=0;i<exp.length();i++)
    {
        if ( isDigitOrDot(exp[i]) )
        {
            num += exp[i];
        }
        else if ( isSymbol(exp[i]) )
        {
            /* current QChar isSymbol,but num is not empty,so push num in queue*/
            if ( !num.isEmpty() )
            {
                ret.enqueue(num);
                num.clear();
            }

            /* store the sign symbol when current QChar is sign */
            /* eg. -1+(-2+3) */
            if ( isSign(exp[i]) && ( (pre=="") || (pre=="(") || isOperator(pre) ) )
            {
                num +=  exp[i];
            }
            else
            {
                ret.enqueue(exp[i]);
            }
        }

        /* store current Qchar to pre */
        pre = exp[i];
    }

    /* 前面for循环最后一个num没有存到对列中,这里要补充 */
    if ( !num.isEmpty() )
    {
        ret.enqueue(num);
    }

    return ret;
}


/* 中缀转后 *
- 当前元素e为数字：输出
- 当前元素e为元素符
    1 与栈顶运算符进行优先级比较
    2 小于等于:将栈顶元素输出,转步骤1
    3 大于：将当前元素e入栈
- 当前元素e为左括号：入栈
- 当前元素e为右括号
    1 弹出栈顶元素并输出直至栈顶元素为左括号
    2 将栈顶的左括号从栈中弹出
*/
bool CalculatorDec::transform(QQueue<QString> exp, QQueue<QString> &output)
{
    bool ret = match(exp);
    QStack<QString> stack;

    output.clear();

    while ( ret && !exp.isEmpty() )
    {
        QString e = exp.dequeue();

        if ( isNumber(e) ) // 若为数字则入队
        {
            output.enqueue(e);
        }
        else if ( isOperator(e) ) // 若为操作符
        {
            /*
              1 与栈顶运算符进行优先级比较
              2 小于等于:将栈顶元素输出,转步骤1
              3 大于：将当前元素e入栈
            */
            while ( !stack.isEmpty() && (priority(e)<=priority(stack.top())) )
            {
                output.enqueue( stack.pop() );
            }
            stack.push(e);
        }
        else if ( isLeft(e) ) // 若为左括号则入栈
        {
            stack.push(e);
        }
        else if ( isRight(e) ) // 若为右括号则出栈
        {
            /*
                1 弹出栈顶元素并输出直至栈顶元素为左括号
                2 将栈顶的左括号从栈中弹出
            */
            while ( !stack.isEmpty() && !isLeft(stack.top()) )
            {
                output.enqueue(stack.pop());
            }
            if ( !stack.isEmpty() )
            {
                stack.pop();
            }

        }
        else
        {
            ret = false;
        }
    }

    while (!stack.isEmpty())
    {
        output.enqueue(stack.pop());
    }

    if (!ret) // 出错则输出也要清空
    {
        output.clear();
    }

    return ret;
}

QString CalculatorDec::calculate(QString l, QString op, QString r)
{
    QString ret = "Error";

    if ( isNumber(l) && isNumber(r) )
    {
        double lp = l.toDouble();
        double rp = r.toDouble();

        if ( op=="+")
        {
            ret = QString::asprintf("%f",lp+rp);
        }
        else if ( op=="-" )
        {
            ret = QString::asprintf("%f",lp-rp);
        }
        else if ( op=="*" )
        {
            ret = QString::asprintf("%f",lp*rp);
        }
        else if ( op=="/" )
        {
            const double P=0.00000001;
            if (-P<rp && rp<P )
            {
                ret = "Error";
            }
            else
            {
                ret = QString::asprintf("%f",lp/rp);
            }
        }
    }

    return ret;
}

/*
    while( !exp.isEmpty() )
    {
        若当前元素为数字，则入栈
        若当前元素为运算符
            1 从栈中弹出右操作数
            2 从栈中弹出左操作数
            3 根据运算符运算
            4 将运算结果压入栈中
        若为其他则表达式有误
    }

*/
QString CalculatorDec::calculate(QQueue<QString> &exp)
{
    QString ret = "Error";
    QStack<QString> stack;

    while( !exp.isEmpty() )
    {
        QString e = exp.dequeue();

        if ( isNumber(e) )
        {
            stack.push(e);
        }
        else if ( isOperator(e) )
        {
            QString rp = !stack.isEmpty() ? stack.pop() : "";
            QString lp = !stack.isEmpty() ? stack.pop() : "";
            QString result = calculate(lp,e,rp);

            if ( result != "Error" )
            {
                stack.push(result);
            }
            else
            {
                break;
            }

        }
        else
        {
            break;
        }
    }


    if ( exp.isEmpty() && (stack.size()==1) && isNumber(stack.top()) )
    {
        ret =  stack.pop();
    }


    return ret;
}

bool CalculatorDec::expression(const QString exp)
{
    bool ret = false;
    QQueue<QString> spExp = split(exp);
    QQueue<QString> postExp;

    if ( transform(spExp,postExp) )
    {
        m_result = calculate(postExp);

        ret = (m_result!="Error");
    }
    else
    {
        m_result = "Error";
    }

    return ret;
}

QString CalculatorDec::result()
{
    return m_result;
}
